package com.lanqiao.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;


public class PolandNotation {

	public static void main(String[] args) {
		//中缀表达式转换为逆波兰表达式
		/*具体步骤如下:
			1)初始化两个栈:运算符栈s1和储存中间结果的栈s2;2)从左至右扫描中缀表达式;
			3)遇到操作数时，将其压s2;
			4)遇到运算符时，比较其与s1栈顶运算符的优先级:
				1.如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈;
				2.否则，若优先级比栈顶运算符的高，也将运算符压入s1;
				3.否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较;
			5)遇到括号时:
				(1)如果是左括号“(”，则直接压入s1
				(2)如果是右括号“)”，则依次弹出 s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃6)重复步骤2至5，直到表达式的最右边
			7)将s1中剩余的运算符依次弹出并压入s2
			8)依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式
		*/
		String expression = "1+((2+3)*4)-5";
		//中缀表达式[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
		List<String> infixExpressionList = toInfixExpressionList(expression);
		System.out.println(infixExpressionList);
		List<String> parseSuffixExpressionList = parseSuffixExpressionList(infixExpressionList);
		System.out.println(parseSuffixExpressionList);
		System.out.println(calculate(parseSuffixExpressionList));
		
		
		
		
		
		
		/*
		//创建逆波兰表达式
		//(30+4)/2-6 == 30 4 + 2 / 6 -
		//方便用空格隔开
		String suffixExpression = "30 4 + 2 / 6 -";
		//思路
		//1. 将3 4 + 5 * 6 -放入ArrayList中
		//2. 将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
		
		List<String> rpnList = getListString(suffixExpression);
		System.out.println(rpnList);
		
		int res = calculate(rpnList);
		System.out.println("计算结果res=" + res);
		*/
	}
	
	//将得到的List转换成对应的后缀表达式
	public static List<String> parseSuffixExpressionList(List<String> ls) {
		//定义两个栈
		Stack<String> s1 = new Stack<>();//符号栈
		//说明:因为s2这时栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
		//因此比较麻烦，这里我们就不用Stack<String〉直接使用List<String> s2
		//stack<String> s2 = new Stack<String>();//储存中间结果的栈s2
		List<String> s2 = new ArrayList<>();//储存中间结果的List2
		
		//遍历ls
		for (String item : ls) {
			//如果是一个数，加入s2
			if (item.matches("\\d+")) {
				s2.add(item);
			}else if (item.equals("(")) {//左括号直接加入
				s1.add(item);
			}else if (item.equals(")")) {
				//如果是右括号"")”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
				while (!s1.peek().equals("(")) {
					s2.add(s1.pop());
				}
				s1.pop();//将左括号弹出
			}else {
				//当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
				while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
					s2.add(s1.pop());
				}
				//最后将item压入栈
				s1.add(item);
			}
		}
		//将s1中剩余的运算符依次弹出并加入s2
		while (s1.size() != 0) {
			s2.add(s1.pop());
		}
		
		return s2;//最后全部的字符存储到s2中
	}
	
	
	//将中缀表达式转换成对应的List
	public static List<String> toInfixExpressionList(String s) {
		//定义一个List，存放中缀表达式对应的内容
		List<String> ls = new ArrayList<>();
		int i = 0;//这是一个指针，用于遍历中缀表达式字符串
		String str;//对多位数的拼接
		char c;//每遍历到一个字符，就放到c
		do {
			//如果c是一个非数字，就需要加入到ls
			//ASCII 0 == 48 9 == 57
			if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
				ls.add("" + c);//转String
				i++;//后移
			}else {//如果是数，需要考虑是否是多位数
				str = "";
				while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
					str += c;//数字拼接
					i++;//后移
				}
				ls.add(str);
			}
		} while (i < s.length());
		return ls;
	}
	
	
	//将一个逆波兰表达式，依次将数据和运算符放入到ArrayList中
	public static List<String> getListString(String suffixExpression) {
		//将suffixExpression分割
		String[] split = suffixExpression.split(" ");
		List<String> list = new ArrayList<String>();
		for (String ele : split) {
			list.add(ele);
		}
		return list;
	}
	
	///完成对逆波兰表达式的运算/*
	/*
	1)从左至右扫描,将3和4压入堆栈;
	2)遇到+运算符，因此弹出4和3(4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈;3)将5入栈;
	4)接下来是*运算符,因此弹出5和7，计算出7>5=35，将35入栈;5)将6入栈;
	6)最后是-运算符,计算出35-6的值,即29，由此得出最终结果
	*/
	public static int calculate(List<String> ls) {
		//创建栈
		Stack<String> stack = new Stack<String>();
		//遍历ls
		for (String item : ls) {
			//这里使用正则表达式来取出数
			if (item.matches("\\d+")) {
				stack.push(item);
			}else {
				//pop两个数，并运算，再入栈
				int num1 = Integer.parseInt(stack.pop());
				int num2 = Integer.parseInt(stack.pop());
				int res = 0;
				if (item.equals("+")) {
					res = num1 + num2;
				}else if (item.equals("-")) {
					res = num2 - num1;
				}else if(item.equals("*")) {
					res = num1 * num2;
				}else if (item.equals("/")) {
					res = num2 / num1;
				}else {
					throw new RuntimeException("运算符有误！");
				}
				//因为stack<String>,所以需要转换一下
				stack.push("" + res);
			}
		}
		//最后留在stack的数据为运算结果
		return Integer.parseInt(stack.pop());
	}
	
}


//编写一个类Operation返回运算符对应的优先级
class Operation {
	private static final int ADD = 1;
	private static final int SUB = 1;
	private static final int MUL = 1;
	private static final int DIV = 1;
	
	//返回对应的优先级数字
	public static int getValue(String operation) {
		int res = 0;
		switch (operation) {
		case "+":
			res = ADD;
			break;
		case "-":
			res = SUB;
			break;
		case "*":
			res = MUL;
			break;
		case "/":
			res = DIV;
			break;
		default:
			break;
		}
		return res;
	}
}
